package com.tom.myjni.mds.structure.graph;

import android.os.Build;
import android.util.Log;
import androidx.annotation.RequiresApi;
import java.util.ArrayDeque;

/**
 * Created by hcDarren on 2018/11/11.
 * 图。
 */
@RequiresApi(api = Build.VERSION_CODES.GINGERBREAD)
public class Graph {
    public final static int MAX_WEIGHT = 65536;
    // 顶点的个数
    int vertexSize;
    // 顶点的集合
    int[] vertexes;
    // 边的集合
    int[][] matrix;

    public Graph(int vertexSize, int[] vertexes, int[][] matrix) {
        this.vertexSize = vertexSize;
        this.vertexes = vertexes;
        this.matrix = matrix;
    }

    // 广度优先 遍历图。
    public void breadthFirstSearch() {
        // 访问过的顶点 的角标集合，被访问过设置true
        boolean[] visited = new boolean[vertexSize];

        // 把第一个顶点加入队列中
        ArrayDeque<Integer> vertexQ = new ArrayDeque<>();
        vertexQ.push(vertexes[3]); // 图中最上面的顶点。

        while (!vertexQ.isEmpty()) {
            // 当前顶点，但是同时我们这里又是角标
            int currentVertex = vertexQ.removeFirst(); // 弹出来，并移除
            // 查询当前的角标
            int index = currentVertex;

            if (!visited[index]) { // O(1) 没有被访问过，就立即访问它
                Log.e("TAG", "访问到了顶点：" + currentVertex);
                visited[index] = true; // 标记index访问过了

                // 将它相连的所有节点，
                for (int i = 0; i < vertexSize; i++) {
                    if (matrix[index][i] == 1 && !visited[i]) {// 代表与 index元素 相连，且没被访问过。加入队列中。
                        // 还可以写一个判断，如果队列中不包含 再往里面新增 , 画蛇添足
                        // if(!vertexQ.contains(vertexes[i])) {  // 0(N)
                        vertexQ.addLast(vertexes[i]);
                        // }
                    }
                }
            }
        } // end-while
    }

    //普里姆算法：最小生成树，有权值的无向图。
    // 每次都找最近的，与它相连的考虑进来，变修路边淘汰。
    public void prim() {
        // 定义一个数组内存，当前已修好的村庄 , lowcost = 0 代表已经修了
        int[] lowcost = new int[vertexSize]; // lowcost[idx]=0，表示已经修好了

        // 第0列的数据先放到 lowcost，考虑进来
        for (int i = 0; i < vertexSize; i++) {
            lowcost[i] = matrix[0][i];
        }
        int sum = 0; // 总的最短路径

        for (int i = 1; i < vertexSize; i++) { // i=1,因为自己不要考虑
            int min = MAX_WEIGHT; // 最小值
            int minId = 0;        // 最小的id值

            // 1.找最小的 ，且他们之间是否联通
            for (int j = 1; j < vertexSize; j++) {
                if (lowcost[j] < min && lowcost[j] != 0) {
                    min = lowcost[j]; // 找出最小的非零值。
                    minId = j;        // 目标村庄index
                }
            }
            Log.e("TAG", "找到村庄：" + vertexes[minId] + " , 修路距离：" + min);
            lowcost[minId] = 0; // 标记已修好了，将最小的非零值设置为0.
            sum += min; // +最小的边

            // 这个代码有问题
            for (int k = 0; k < vertexSize; k++) {
                // 2.边考虑边淘汰：有更小的非零值  替换lowcost[k]的值。
                // 谁的值大，淘汰谁
                if (matrix[minId][k] < lowcost[k] && lowcost[k] > 0) {
                    lowcost[k] = matrix[minId][k];
                }
            }
            /*for (int number : lowcost) {
                Log.e("TAG","number = "+number); // 打印当前里面的路径。
            }
            Log.e("TAG","==================================== ");*/
        }
        Log.e("TAG", "最短的路径是：" + sum);
    }

    // 迪杰斯特拉：找最短路径
    public void dijstra() {
        // 最短路径 ， 有没有找到最短距离
        // 有没找到最短路径
        boolean[] isPath = new boolean[vertexSize];
        // 存放每个村庄的最短路径结果
        int[] shortPath = new int[vertexSize];
        // 第一列的数据先放到 shortPath
        for (int i = 0; i < vertexSize; i++) {
            shortPath[i] = matrix[0][i];
        }

        shortPath[0] = 0; // 到自己的距离是0
        isPath[0] = true; // 已经找到了
        int minId = 0;    //

        for (int i = 1; i < vertexSize; i++) { // 每个村庄都要找
            int min = MAX_WEIGHT;
            for (int j = 1; j < vertexSize; j++) { // 找最小的
                // 当前有没有被找到过？
                if (!isPath[j] && shortPath[j] < min) { // 没被找到过，且比min小。
                    minId = j;
                    min = shortPath[j]; // 找到最小值
                }
            }
            isPath[minId] = true; // 找到了

            for (int j = 0; j < vertexSize; j++) {
                if (!isPath[j] && (min + matrix[minId][j]) < shortPath[j]) {
                    // 当前距离+最小值，仍然小于已找到的最短距离，更新最短距离。
                    shortPath[j] = min + matrix[minId][j];
                }
            }
            for (int k = 0; k < vertexSize; k++) {
                Log.e("TAG", shortPath[k] + " ");
            }
            Log.e("TAG", "==========打印遍历之后的结果=========:" + i);
        }
        for (int i = 0; i < vertexSize; i++) {
            Log.e("TAG", "顶点 0 到顶点 " + i + " 的最短距离为：" + shortPath[i]);
        }
    }
    /**
     * 思想：
     *
     */
}
